doi: 10.3934/jimo.2017076

Multi-machine scheduling with interval constrained position-dependent processing times

1. 

College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, China

2. 

Department of Information Management, National Formosa University, YunLin 63201, Taiwan

3. 

College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, China

* Corresponding author: Dar-Li Yang

Received  September 2016 Revised  December 2016 Published  September 2017

Fund Project: The first author is supported by the Fundamental Research Fund for the Central Universities No. XAA16077

This paper investigates multi-machine scheduling problems with interval constrained actual processing times. The actual processing time of each job is assumed to be restricted in a given interval otherwise the extra earliness or tardiness time should be used to patch up the flaw of job. The objectives are to find the optimal job sequence to minimize the total load of machines, the number of exceeding-interval jobs and the makespan of job schedule, respectively. This paper shows that both of the total load minimization problem and the exceeding job number minimization problem are polynomially solvable. For the makespan minimization problem, this paper proves that it is NP-hard, and proposes a fully polynomial time approximation scheme (FPTAS) for the case with two parallel machines.

Citation: Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2017076
References:
[1]

D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178. doi: 10.1016/S0377-2217(98)00246-X.

[2]

F. Bourgeois and J. C. Lassalle, An extension of the munkres algorithm for the assignment problem to rectangular matrices, Communications of the ACM, 14 (1971), 802-804. doi: 10.1145/362919.362945.

[3]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498.

[4]

H. ChenC. Chu and J. M. Proth, Cyclic scheduling of a hoist with time window constraints, IEEE Transactions on Robotics and Automation, 14 (1998), 144-152.

[5]

Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, 194 (2009), 18-27. doi: 10.1016/j.ejor.2007.11.047.

[6]

S. ChubanovM. Y. Kovalyov and E. Pesch, An fptas for a single-item capacitated economic lot-sizing problem with monotone cost structure, Mathematical Programming, 106 (2006), 453-466. doi: 10.1007/s10107-005-0641-0.

[7]

D. W. EngelsD. R. KargerS. G. KolliopoulosS. SenguptaR. Uma and J. Wein, Techniques for scheduling with rejection, Journal of Algorithms, 49 (2003), 175-191. doi: 10.1016/S0196-6774(03)00078-6.

[8]

G. FinkeA. Gara-AliM. L. EspinouseV. Jost and J. Moncel, Unified matrix approach to solve production-maintenance problems on a single machine, Omega, 66 (2017), 140-146. doi: 10.1016/j.omega.2016.02.005.

[9]

R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45 (1966), 1563-1581. doi: 10.1002/j.1538-7305.1966.tb01709.x.

[10]

J. N. D Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers & Industrial Engineering, 14 (1988), 387-393. doi: 10.1016/0360-8352(88)90041-1.

[11]

G. Hardy, J. Littlewood and G. Polya, Inequalities, Cambridge Univ. Press, london, 1965.

[12]

M. Ji and T. C. E. Cheng, Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information Processing Letters, 110 (2010), 460-463. doi: 10.1016/j.ipl.2010.04.015.

[13]

M. JiC. J. Hsu and D.-L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Journal of Combinatorial Optimization, 26 (2013), 437-447. doi: 10.1007/s10878-011-9415-1.

[14]

W. H. Kuo and D. L. Yang, Minimizing the makespan in a single-machine schedul-ing problem with the cyclic process of an aging effect, Journal of the Operational Re-search Society, 59 (2008), 416-420.

[15]

M. LiuF. ZhengC. Chu and J. Zhang, An fptas for uniform machine scheduling to minimize makespan with linear deterioration, Journal of Combinatorial Optimization, 23 (2012), 483-492. doi: 10.1007/s10878-010-9364-0.

[16]

G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Re-search, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979.

[17]

G. Mosheiov, A note: Multi-machine scheduling with general position-based de-terioration to minimize total load, International Journal of Production Economics, 135 (2012), 523-525. doi: 10.1016/j.ijpe.2011.09.005.

[18]

G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147 (2003), 665-670. doi: 10.1016/S0377-2217(02)00358-2.

[19]

J. Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics, 5 (1957), 32-38. doi: 10.1137/0105003.

[20]

M. Pinedo, Scheduling, Springer-Verlag, New York, 2012.

[21]

S. K. Sahni, Algorithms for scheduling independent tasks, Journal of the ACM, 23 (1976), 116-127. doi: 10.1145/321921.321934.

[22]

G. Steiner and R. Zhang, Revised delivery-time quotation in scheduling with tardi-ness penalties, Operations research, 59 (2011), 1504-1511. doi: 10.1287/opre.1110.0948.

[23]

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)?, INFORMS Journal on Computing, 12 (2000), 57-74. doi: 10.1287/ijoc.12.1.57.11901.

[24]

P. XueY. Zhang and X. Yu, Single-machine scheduling with piece-rate mainte-nance and interval constrained position-dependent processing times, Applied Mathemat-ics and Computation, 226 (2014), 415-422. doi: 10.1016/j.amc.2013.10.034.

[25]

P. YanA. CheX. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Computers & Operations Research, 50 (2014), 128-140. doi: 10.1016/j.cor.2014.04.002.

[26]

P. YanA. CheN. Yang and C. Chu, A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem, International Journal of Production Research, 50 (2012), 6403-6418. doi: 10.1080/00207543.2011.645953.

[27]

P. YanC. ChuN. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480. doi: 10.1080/00207540903225205.

[28]

Y. YinT. ChengJ. XuS. R. Cheng and C. C. Wu, Single-machine schedul-ing with past-sequence-dependent delivery times and a linear deterioration, Journal of Industrial and Management Optimization, 9 (2013), 323-339. doi: 10.3934/jimo.2013.9.323.

[29]

X. Yu and Y. Zhang, Single machine scheduling with aging effect and upper-bounded actual processing times, Arabian Journal for Science and Engineering, 39 (2014), 1489-1495. doi: 10.1007/s13369-013-0716-9.

[30]

X. YuY. Zhang and K. Huang, Multi-machine scheduling with general position-based deterioration to minimize total load revisited, Information Processing Letters, 114 (2014), 399-404. doi: 10.1016/j.ipl.2014.02.009.

[31]

X. ZhangY. Yin and C. C. Wu, Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine, Engineering Optimization, 49 (2017), 84-97. doi: 10.1080/0305215X.2016.1163629.

[32]

Z. ZhouA. Che and P. Yan, A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints, Applied Mathematical Modelling, 36 (2012), 3621-3629. doi: 10.1016/j.apm.2011.10.032.

show all references

References:
[1]

D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178. doi: 10.1016/S0377-2217(98)00246-X.

[2]

F. Bourgeois and J. C. Lassalle, An extension of the munkres algorithm for the assignment problem to rectangular matrices, Communications of the ACM, 14 (1971), 802-804. doi: 10.1145/362919.362945.

[3]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498.

[4]

H. ChenC. Chu and J. M. Proth, Cyclic scheduling of a hoist with time window constraints, IEEE Transactions on Robotics and Automation, 14 (1998), 144-152.

[5]

Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, 194 (2009), 18-27. doi: 10.1016/j.ejor.2007.11.047.

[6]

S. ChubanovM. Y. Kovalyov and E. Pesch, An fptas for a single-item capacitated economic lot-sizing problem with monotone cost structure, Mathematical Programming, 106 (2006), 453-466. doi: 10.1007/s10107-005-0641-0.

[7]

D. W. EngelsD. R. KargerS. G. KolliopoulosS. SenguptaR. Uma and J. Wein, Techniques for scheduling with rejection, Journal of Algorithms, 49 (2003), 175-191. doi: 10.1016/S0196-6774(03)00078-6.

[8]

G. FinkeA. Gara-AliM. L. EspinouseV. Jost and J. Moncel, Unified matrix approach to solve production-maintenance problems on a single machine, Omega, 66 (2017), 140-146. doi: 10.1016/j.omega.2016.02.005.

[9]

R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45 (1966), 1563-1581. doi: 10.1002/j.1538-7305.1966.tb01709.x.

[10]

J. N. D Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers & Industrial Engineering, 14 (1988), 387-393. doi: 10.1016/0360-8352(88)90041-1.

[11]

G. Hardy, J. Littlewood and G. Polya, Inequalities, Cambridge Univ. Press, london, 1965.

[12]

M. Ji and T. C. E. Cheng, Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information Processing Letters, 110 (2010), 460-463. doi: 10.1016/j.ipl.2010.04.015.

[13]

M. JiC. J. Hsu and D.-L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Journal of Combinatorial Optimization, 26 (2013), 437-447. doi: 10.1007/s10878-011-9415-1.

[14]

W. H. Kuo and D. L. Yang, Minimizing the makespan in a single-machine schedul-ing problem with the cyclic process of an aging effect, Journal of the Operational Re-search Society, 59 (2008), 416-420.

[15]

M. LiuF. ZhengC. Chu and J. Zhang, An fptas for uniform machine scheduling to minimize makespan with linear deterioration, Journal of Combinatorial Optimization, 23 (2012), 483-492. doi: 10.1007/s10878-010-9364-0.

[16]

G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Re-search, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979.

[17]

G. Mosheiov, A note: Multi-machine scheduling with general position-based de-terioration to minimize total load, International Journal of Production Economics, 135 (2012), 523-525. doi: 10.1016/j.ijpe.2011.09.005.

[18]

G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147 (2003), 665-670. doi: 10.1016/S0377-2217(02)00358-2.

[19]

J. Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics, 5 (1957), 32-38. doi: 10.1137/0105003.

[20]

M. Pinedo, Scheduling, Springer-Verlag, New York, 2012.

[21]

S. K. Sahni, Algorithms for scheduling independent tasks, Journal of the ACM, 23 (1976), 116-127. doi: 10.1145/321921.321934.

[22]

G. Steiner and R. Zhang, Revised delivery-time quotation in scheduling with tardi-ness penalties, Operations research, 59 (2011), 1504-1511. doi: 10.1287/opre.1110.0948.

[23]

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)?, INFORMS Journal on Computing, 12 (2000), 57-74. doi: 10.1287/ijoc.12.1.57.11901.

[24]

P. XueY. Zhang and X. Yu, Single-machine scheduling with piece-rate mainte-nance and interval constrained position-dependent processing times, Applied Mathemat-ics and Computation, 226 (2014), 415-422. doi: 10.1016/j.amc.2013.10.034.

[25]

P. YanA. CheX. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Computers & Operations Research, 50 (2014), 128-140. doi: 10.1016/j.cor.2014.04.002.

[26]

P. YanA. CheN. Yang and C. Chu, A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem, International Journal of Production Research, 50 (2012), 6403-6418. doi: 10.1080/00207543.2011.645953.

[27]

P. YanC. ChuN. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480. doi: 10.1080/00207540903225205.

[28]

Y. YinT. ChengJ. XuS. R. Cheng and C. C. Wu, Single-machine schedul-ing with past-sequence-dependent delivery times and a linear deterioration, Journal of Industrial and Management Optimization, 9 (2013), 323-339. doi: 10.3934/jimo.2013.9.323.

[29]

X. Yu and Y. Zhang, Single machine scheduling with aging effect and upper-bounded actual processing times, Arabian Journal for Science and Engineering, 39 (2014), 1489-1495. doi: 10.1007/s13369-013-0716-9.

[30]

X. YuY. Zhang and K. Huang, Multi-machine scheduling with general position-based deterioration to minimize total load revisited, Information Processing Letters, 114 (2014), 399-404. doi: 10.1016/j.ipl.2014.02.009.

[31]

X. ZhangY. Yin and C. C. Wu, Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine, Engineering Optimization, 49 (2017), 84-97. doi: 10.1080/0305215X.2016.1163629.

[32]

Z. ZhouA. Che and P. Yan, A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints, Applied Mathematical Modelling, 36 (2012), 3621-3629. doi: 10.1016/j.apm.2011.10.032.

[1]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2016.12.771

[2]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2015.11.685

[3]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, doi: 10.3934/naco.2015.5.71

[4]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2018017

[5]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2014.10.613

[6]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2009.5.95

[7]

Bin Dan, Huali Gao, Yang Zhang, Ru Liu, Songxuan Ma. Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2017041

[8]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2016.12.703

[9]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2017057

[10]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2014.10.1071

[11]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2005.1.353

[12]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2014.10.591

[13]

Chuanli Zhao. An FPTAS for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2016033

[14]

Alexander Khapalov. Controllability properties of a vibrating string with variable axial load. Discrete & Continuous Dynamical Systems - A, doi: 10.3934/dcds.2004.11.311

[15]

Soumya Kundu, Soumitro Banerjee, Damian Giaouris. Vanishing singularity in hard impacting systems. Discrete & Continuous Dynamical Systems - B, doi: 10.3934/dcdsb.2011.16.319

[16]

Frédéric Lebon, Raffaella Rizzoni. Modeling a hard, thin curvilinear interface. Discrete & Continuous Dynamical Systems - S, doi: 10.3934/dcdss.2013.6.1569

[17]

Viktor I. Gerasimenko, Igor V. Gapyak. Hard sphere dynamics and the Enskog equation. Kinetic & Related Models, doi: 10.3934/krm.2012.5.459

[18]

Sergei A. Avdonin, Boris P. Belinskiy. On controllability of a linear elastic beam with memory under longitudinal load. Evolution Equations & Control Theory, doi: 10.3934/eect.2014.3.231

[19]

Domokos Szász. Algebro-geometric methods for hard ball systems. Discrete & Continuous Dynamical Systems - A, doi: 10.3934/dcds.2008.22.427

[20]

Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2007.3.685

2016 Impact Factor: 0.994

Metrics

  • PDF downloads (3)
  • HTML views (68)
  • Cited by (0)

Other articles
by authors

[Back to Top]