The just-in-time scheduling problem in a flow-shop scheduling system

• Published in: European journal of operational research 2012-02, Vol.216 (3), p.521-532
• Main Author: Shabtay, Dvir
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Approximation; Complexity; Customers; Exact sciences and technology; Flow-shop; Gain; Inventory control, production control. Distribution; Job shops; Just in time; Just-in-time scheduling; Mathematical analysis; Mathematical programming; No-wait restriction; Operational research; Operational research and scientific management; Operational research. Management science; Optimization; Optimization algorithms; Production scheduling; Pseudo-polynomial time algorithm; Scheduling; Scheduling, sequencing; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2011.07.053

► We study several variants of the problem of maximizing the weighted number of JIT jobs in a flow-shop scheduling system. ► We show that the unweighted version of the problem on two machines is solvable in O( n 3) time. ► We show that the problem is ordinary NP-hard even if the processing times are machine-independent. ► We show that the case of job-independent processing times is solvable in polynomial time. ► A polynomial time solution is provided for the problem under a no-wait restriction. We study the problem of maximizing the weighted number of just-in-time ( JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O( n 3) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP -hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O( n 3) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O( n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O( mn 2) time optimization algorithm.